package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.ArrayUtils;
import com.xsherl.leetcode.utils.PrintUtils;

public class Search2dMatrix {

    /**
     * 二分查找法
     * 将二维数组视为按行组合在一起的一维数组，然后使用二分查找法查找元素
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int begin = 0, end = m * n - 1;
        while (begin <= end){
            int mid = (begin + end) / 2;
            int r = mid / n;
            int c = mid % n;
            PrintUtils.println("====", mid, begin, end, r, c);
            if (matrix[r][c] < target){
                begin = mid + 1;
            } else if (matrix[r][c] > target){
                end = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = ArrayUtils.parseArray("" +
                "[[1]]\n" +
                "", int[].class);
        int target = 1;
        PrintUtils.println(matrix);
        boolean b = new Search2dMatrix().searchMatrix(matrix, target);
        System.out.println(b);
    }
}
